1. Technical Field of the Invention
The present invention relates to communications and, in particular, to encrypting communications for transmission over unsecured communications channels using public key/private key techniques.
2. Description of Related Art
Communications take place over many different types of channel media such as wireline, radio frequency, fiber optic, and the like. The communications carried over each of these media are, however, subject to interception (commonly referred to as "eavesdropping"). In instances where a communication concerns sensitive or proprietary information, it is common for the parties to the communication to employ a security protocol (such as encryption or scrambling) in order to prevent the eavesdropper from being able to discover the communicated information.
In encryption, a plaintext message is encrypted by a sender into a ciphertext message using a key (cryptovariable) and then sent over a communications channel. A receiver then decrypts the communications channel transmitted ciphertext message using the same key. An eavesdropper, who presumably does not have access to the key, cannot decrypt the transmitted ciphertext message to recover the plaintext message. Any sensitive or proprietary information contained within the plaintext message is thus safely communicated.
It is not unusual for the sender and receiver to be located at a considerable distance from each other. In such cases, a number of problems arise in ensuring that the designated key necessary for decryption is securely communicated to the receiver. A secure channel, such as a courier service, may be used to communicate the key. However, such channels tend to be expensive, slow, and perhaps even unsecured in instances where the trustworthiness of the courier is compromised.
To address this problem of key distribution, public key methods have been developed for security protocols wherein a sender and receiver may independently determine a common secret key by exchanging information based on secret parameters known only to them. The information that is exchanged is known as "public keys", and although subject to intervention the common secret key cannot be determined by the eavesdropper without having access to the secret parameters. One such well known public key encryption scheme is the Diffie-Hellman algorithm. See, U.S. Pat. No. 4,200,770, to Hellman, et al. and U.S. Pat. No. 4,218,582, to Hellman, et al.
Reference is now made to FIGS. 1 and 2 wherein FIG. 1 is a block diagram of a secure communications system 10 in accordance with the prior art which implements the Diffie-Hellman public key encryption technique, and FIG. 2 is a signal flow diagram illustrating prior art key exchange, encrypted data communication, and re-synchronization processes. There are two parties, Party A and Party B, to a conversation which is being carried over an unsecured communications channel 11 supported by, for example, a wireline, radio frequency, fiber optic, or the like, communications link. Each party has access to a security device 12 positioned at opposite ends of the communications channel 11. Each security device includes a random number generator 14, a key generator 16 and an encryption/decryption device 18 (implementing a stream cipher such as RC4). The encrypting/decrypting device 18 comprises a cipher stream generator 20 and an exclusive OR (XOR) multiplier 22.
A data communication (perhaps comprising digitized speech or data in the form of data packets) referred to as plaintext (PT) is being carried between Party A and Party B on lines 24 and over the channel 11. At this point in time, plaintext is being passed directly (i.e., without encryption) through the encrypting/decrypting device 18. It is then decided to encrypt the communication. The random number generator 14 of the security device 12A for Party A produces a secret random quantity y. Key generator 16 then generates two public quantities:
a, referred to as a base vector, which is an integer; and
p, referred to as a modulus, which is a prime number larger than a.
From these public quantities and the secret random quantity, the key generator 16 for Party A generates a public key PK.sub.A in accordance with the following: EQU PK.sub.A =a.sup.Y mod p (1)
The security device 12A then initiates a key exchange with the security device 12B for Party B. A triplet (a,p,PK.sub.A) is sent by the security device 12A to the security device 12B over the communications channel 11 in a key exchange message (IKE). It will be understood that to the extent a and p are previously agreed upon by Party A and Party B, they do not need to be included in the key exchange message. It will be noted here that the key exchange message is being sent without encryption. However, this is of no concern as the function for computing PK.sub.A is a one-way function (i.e., it is mathematically impossible for an eavesdropper to determine the secret random quantity y from knowledge of PK.sub.A).
In response to the key exchange message, the security device 12B for Party B has its random number generator 14 produce a secret random quantity x. Key generator 16 then generates for Party B a public key PK.sub.B in accordance with the following: EQU PK.sub.B =a.sup.x mod p (2)
The security device 12B then completes the key exchange with the security device 12A for Party A. The public key (PK.sub.B) is sent by the security device 12B to the security device 12A over the communications channel 11 in a key exchange response message (EKE). It will be noted again that the key exchange response message is being sent without encryption. Again, this is of no concern as the function for computing PK.sub.B is a one-way function, and thus the eavesdropper cannot utilize mathematical processing to determine the secret random quantity x from knowledge of PK.sub.B.
The key generators 16 of the security devices 12 for Party A and Party B now independently generate a shared private key K in accordance with the following: EQU K=a.sup.xy mod p (3)
The key generator 16 for the Party A security device 12A generates K as follows: EQU K=a.sup.xy mod p=PK.sub.B a.sup.y mod p (4)
Similarly, the key generator 16 for the Party B security device 12B generates K as follows: EQU K=a.sup.xy mod p=PK.sub.A a.sup.x mod p (5)
While the security devices 12A and 12B are able to independently generate the same secret key K, it will be recognized that an eavesdropper is unable to compute the private key, in spite of having access to the public keys PK.sub.A and PK.sub.B, because knowledge of the necessary secret random quantities x and y is unknown and cannot be mathematically determined. The private keys K are then applied to initialize the cipher stream generators 20 which output a cipher stream C that is either exclusively ORed 22 with the plaintext (PT) to generate ciphertext (CT) for transmission over the channel 11, or exclusively ORed with received ciphertext to generate the original plaintext.
For a bi-directional data communication between Party A and Party B as illustrated in FIG. 1, the secret key K actually comprises (i.e., may be split into) two keys K.sub.AB and K.sub.BA. The first private key K.sub.AB is used by security device 12A to generate a cipher stream for encrypting Party A data communications, and by security device 12B to generate a cipher stream for decrypting Party A data communications. Conversely, the second private key K.sub.BA is used by security device 12B to generate a cipher stream for encrypting Party B data communications, and by security device 12A to generate a cipher stream for decrypting Party B data communications. The need for two private keys when handling bi-directional communications is required to ensure that the same generated cipher stream is never used for the encryption of different plaintext sequences.
Once the cipher stream generators 20 are initialized with the appropriate private key K, they must remain synchronized in order to ensure proper conversion between plaintext and ciphertext. The communications channel accordingly must be able to guarantee an ordered (i.e., correctly sequenced) delivery of any encrypted sequenced data packets so that synchronization may be maintained. In the event synchronization is lost, for example due to a loss of an encrypted data packet during transmission over the channel 11, re-synchronization followed by encryption with a new private key must occur. This is so because the recovery of plaintext is easily accomplished with knowledge of two different plaintext messages encrypted with the same cipher stream C (i.e., produced from the same private key K).
Re-synchronization then requires a new exchange of public keys, followed by the independent generation of another private key and appropriate initialization of the cipher stream generators 20. This process is undesirable as it significantly delays completion of the data communication and consumes valuable communications resources (i.e., wastes bandwidth) on the channel 11 during the key exchange that could otherwise be used in carrying communications which generate revenue. Furthermore, if one of the parties to the communication comprises a mobile communications device (such as a cellular telephone) the computation of the private key is a processor intensive operation requiring a significant time expenditure and causing a significant drain on battery power resources.
The incidence of encrypted data packet loss necessitating re-synchronization is especially high in connection with those communications channels 11, such as wireless radio frequency communications channels, which suffer from interference, distortion or fading. In fact, a five to ten percent data packet loss rate in connection with the use of wireless communications channels is not uncommon. Each instance of packet loss in connection with encrypted sensitive or proprietary information data communications then unfortunately necessitates an inefficient re-synchronization. For sensitive or proprietary information data communications carried over such communications channels, there is a need then for a more efficient and effective security protocol which does not necessarily require re-synchronization in the event of a data packet loss.